package org.example.top40;

import java.util.Scanner;

public class main35 {
    //最长公共子序列
    //输入：text1 = "abcde", text2 = "ace"
    //输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3
    //思路：创建dp二维数组len+1，开始双for循环
    //两char 字符相等对角dp+1 不等 上边和左边取最大值
    //返回 dp[len+1][len+1];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
//        String s1="abcde";
//        String s2="ace";
        int res=longestCommonSub(s1,s2);
        System.out.println(res);
    }
    private static int longestCommonSub(String text1, String text2) {
        int[][] dp=new int[text1.length()+1][text2.length()+1];
        for (int i = 1; i <text1.length()+1 ; i++) {
            char c1=text1.charAt(i-1);
            for (int j = 1; j < text2.length()+1; j++) {
                char c2=text2.charAt(j-1);
                if(c1==c2){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }

}
